# -*- coding:utf-8 -*- 
import copy

class Quad:
    #QUAD TYPES
    Q0 = 0
    Q1 = 1
    Q2 = 2
    Q3 = 3
    Q4 = 4 
    Qd = 5
    
    #QUAD BOARD CELL TYPES
    VALUE_PIECE = 1
    VALUE_EMPTY = 0
    
    #DEBUG FLAG
    DEBUG = False
       
    def __init__(self, index, board):
        self.index =  index #left upper corner of the quad
        self.board = board
        self.type = self.calcQuadType(board)
    
    def __hash__(self):
        return hash((self.index))
    
    def clone(self):
        ###########DEBUG###########
        if self.DEBUG:
            print "Point: ", self.index, ", Quad type: ", self.type
        ###########################
        return Quad(self.index, self.board)
    
    def calcQuadType(self, board = None):
        '''
        @param board: a 2x2 array of the quad
        @return: Quad Type 
        ''' 
        if board is None:
            board = self.board
        count = 0
        for b in board.values():
            count += b
        if count == 0:
            return self.Q0
        if count == 1:
            return self.Q1
        if count == 2:
            if board[(0,0)] == board[(1,1)]:
                return self.Qd
            return self.Q2
        if count == 3:
            return self.Q3
        return self.Q4
    
    def removePiece(self, point):
        '''
        Remove a piece from the quad
        @param point: the position of the piece
        @return: new quad type 
        '''
        relPos = (point[0] - self.index[0], point[1] - self.index[1])
        ###########DEBUG###########
        if self.DEBUG:
            if not self.isLegalBoardKey(relPos):
                print "***\nILLEGAL QUAD BOARD KEY!\nPOINT IS: ", point, "\nINDEX IS:", self.index, "\nKEY IS: ", relPos
                raise Exception
        ###########################
        self.board[relPos] = 0
        self.type = self.calcQuadType(self.board)
        return self.type
    
    def relativePosition(self, point):
        '''
        Get the relative position of the point in the quad cell
        @param point: absalute point position
        @return: relative (row,col) of the point in the quad board 
        '''
        return (point[0] - self.index[0], point[1] - self.index[1])
    
    def addPiece(self, point):
        '''
        Add a piece to the quad
        @param oldPos: the position of the piece
        @return: new quad type 
        '''
        relPos = self.relativePosition(point)
        ###########DEBUG###########
        if self.DEBUG:
            if not self.isLegalBoardKey(relPos):
                print "***\nILLEGAL QUAD BOARD KEY!\nPOINT IS: ", point, "\nINDEX IS:", self.index, "\nKEY IS: ", relPos
                raise Exception
        ###########################            
        self.board[relPos] = 1
        
        self.type = self.calcQuadType(self.board)
        return self.type
    
    def isLegalBoardKey(self, point):
        if point in [(0,0),(0,1),(1,0),(1,1)]:
            return True
        return False
    
    def changeSingleCell(self, point, value):
        '''
        Change the value of a single cell in the quad board
        @param point: absolute point index
        @param value: new value
        @return: new quad type
        ''' 
        relPos = self.relativePosition(point)
        self.board[relPos] = value
        self.type = self.calcQuadType(self.board)
        return self.type
    
    def spin(self):
        '''
        Spin quad 90 degrees clockwise
        @return: quad type  
        '''
        board = dict()
        board[(0,0)] = self.board[(1,0)]
        board[(0,1)] = self.board[(0,0)]
        board[(1,0)] = self.board[(1,1)]
        board[(1,1)] = self.board[(0,1)]
        self.board = board
        return self.type
        
class Quads:
    
    #DEBUG FLAG
    DEBUG = False
    
    def __init__(self, N, board, player):
        #number of quads of each type
        self.quadTypesCounts    = [0,0,0,0,0,0]
        self.quadsDict          = dict()
        self.player             = player
        if not board is None: 
            for i in xrange(-1,N):
                for j in xrange(-1,N):
                    quadBoard = self.getPartialBoard(board, (i,j), player, N)
                    quad = Quad((i,j), quadBoard)
                    self.quadsDict[quad.index] = quad.clone()
        
            #count each quad type
            for quad in self.quadsDict.values():
                self.quadTypesCounts[quad.type] += 1
            
    def clone(self):
        new = copy.deepcopy(self)
        return new
                
    def changeQuads(self, oldPos, newPos):
        '''
        Change the Quads after a move
        @param oldPos: the old position of the piece
        @param newPos: the new position of the piece  
        '''
        #remove piece from quad
        positions = self.getChangedQuadsIndexs(oldPos)
        for point in positions:
            #dec the number of quads of the old type
            self.quadTypesCounts[self.quadsDict[point].type] -= 1
            type = self.quadsDict[point].removePiece(oldPos)
            #inc the number of quads of the new type
            self.quadTypesCounts[self.quadsDict[point].type] += 1
        
        #add piece to quad
        positions = self.getChangedQuadsIndexs(newPos)
        ###########DEBUG###########
        if self.DEBUG:
            print "***DEBUG***\nPoint: ", newPos," Positions: ", positions
        ###########################
        for point in positions:
            #dec the number of quads of the old type
            self.quadTypesCounts[self.quadsDict[point].type] -= 1
            self.quadsDict[point].addPiece(newPos)
            #int the number of quads of the new type
            self.quadTypesCounts[self.quadsDict[point].type] += 1
    
    def getChangedQuadsIndexs(self, point):
        '''
        @param point: change point
        @return: list of point that might have been changed
        '''
        positions = [point, 
                     (point[0]-1, point[1]), 
                     (point[0],point[1]-1),
                     (point[0]-1,point[1]-1)]
        return positions
        
    def getPartialBoard(self, board, index, player, N):
        '''
        @param index: (row,col) - the uppder left corner of the quad
        @param board: the game board
        @param player: the player for whom we calculate the quads
        @param N: board size  
        @return: a 2x2 array - the partial board that starts at (x,y)
        '''
        quadBoard = dict()
        row,col = index
        if row < 0:
            quadBoard[(0,0)] = 0
            quadBoard[(0,1)] = 0
            if col < 0:
                quadBoard[(1,0)] = 0
                quadBoard[(1,1)] = self.isPlayersPiece(board[0][0], player)
            else:
                quadBoard[(1,0)] = self.isPlayersPiece(board[0][col], player)
                if col + 1 == N:
                    quadBoard[(1,1)] = 0
                else:
                    quadBoard[(1,1)] = self.isPlayersPiece(board[0][col + 1], player)
        else:
            if col < 0:
                quadBoard[(0,0)] = 0
                quadBoard[(1,0)] = 0
                quadBoard[(0,1)] = self.isPlayersPiece(board[row][col + 1], player)
                if row + 1 == N:
                    quadBoard[(1,1)] = 0
                else:
                    quadBoard[(1,1)] = self.isPlayersPiece(board[row + 1][0], player)                                          
            else:
                flag = False
                quadBoard[(0,0)] = self.isPlayersPiece(board[row][col], player)
                if row + 1 == N:
                    flag = True
                    quadBoard[(1,0)] = 0
                else:
                    quadBoard[(1,0)] = self.isPlayersPiece(board[row + 1][col], player)
                if col + 1 == N:
                    flag = True
                    quadBoard[(0,1)] = 0
                else:
                    quadBoard[(0,1)] = self.isPlayersPiece(board[row][col + 1], player)
                if flag:
                    quadBoard[(1,1)] = 0
                else:
                    quadBoard[(1,1)] = self.isPlayersPiece(board[row + 1][col + 1], player)
        return quadBoard
    
    def isPlayersPiece(self, piece, player):
        '''
        @param piece: the value on the board
        @param player: the player we wish to check
        @return: 1 iff the value is players piece
        '''
        if piece == player:
            return 1
        return 0
    
    def eulerNumber(self):
        '''
        Calculate the euler number of the current board layout. 
        The euler number given by [Sum(Q1) - Sum(Q3) - 2*Sum(Qd)]/4
        @return: Euler Number as an integer  
        '''
        number = self.quadTypesCounts[Quad.Q1] - self.quadTypesCounts[Quad.Q3] \
                    - 2*self.quadTypesCounts[Quad.Qd]
        number = number/4
        return number
    
    def removePiece(self, point):
        '''
        Handles the case of a removal of a piece as a result of eating
        '''
        changedQuads = self.getChangedQuadsIndexs(point)
        for quad in changedQuads:
            type = self.quadsDict[quad].calcQuadType()
            self.quadTypesCounts[type] -= 1
            newType = self.quadsDict[quad].removePiece(point)
            self.quadTypesCounts[newType] += 1
            
    def spin(self, spinPoint, board, player):
        '''
        Change the quads after a spin is applied on *spinPoint
        @param spinPoint: the point where the spin was applied
        @param board: current state of the board
        @param player: the player who's pieces are spinning 
        '''
        positions = self.getSpinChangedQuadsIndexs(spinPoint)
        #foreach quad type - dec it's counter
        for p in positions:
            self.quadTypesCounts[self.quadsDict[p].type] -= 1
        
        ###########DEBUG###########
        if self.DEBUG:
            print "Types count after SPIN dec: ", self.quadTypesCounts 
        ###########################    
        
        #make the changes to quad boards
        oneChange   = self.getOneChangeSpinIndexs(spinPoint)
        twoChanges  = self.getTwoChangesSpinIndexs(spinPoint) 
        for p in positions:
            if p in oneChange:
                #change only one cell in the quad and inc the new quad type counter
                value = self.isPlayersPiece(board[spinPoint[0]][spinPoint[1]], player)
                type = self.quadsDict[p].changeSingleCell(p, value)
                self.quadTypesCounts[type] += 1
                ###########DEBUG###########
                if self.DEBUG:
                    print "----"
                    print "Type variable value: ", type
                    print "single: ", p, " type after change: ", self.quadsDict[p].type 
                    print "SPIN: Types count after single quad inc: ", self.quadTypesCounts 
                ###########################
                continue
            
            if p in twoChanges:
                type = self.changeTwoSpinCells(p,spinPoint,board, player)
                self.quadTypesCounts[type] += 1
                ###########DEBUG###########
                if self.DEBUG:
                    print "----"
                    print "Type variable value: ", type
                    print "two: ", p, " type after change: ", self.quadsDict[p].type
                    print "SPIN: Types count after single quad inc: ", self.quadTypesCounts 
                ###########################
                continue
            
            #spin cell
            type = self.quadsDict[p].spin()
            self.quadTypesCounts[type] += 1
            ###########DEBUG###########
            if self.DEBUG:
                print "----"
                print "spin: ", p, " type after change: ", self.quadsDict[p].type
                print "SPIN: Types count after single quad inc: ", self.quadTypesCounts 
            ###########################
        
    def changeTwoSpinCells(self, quadIndex, spinIndex, board, player):
        '''
        Change a quad that requires two changes after a spin
        
        @param quadIndex:
        @param spinIndex: the index of the spined quad
        @param board: current state of the board
        @param player: the player who's pieces are spinning
        @return: the new type of the quad
        '''
        if quadIndex[0] > spinIndex[0]:
            #lower quad change
            value = self.isPlayersPiece(board[spinIndex[0]][spinIndex[1]+1], player)
            self.quadsDict[quadIndex].changeSingleCell(quadIndex, value)
            nextPoint = (quadIndex[0], quadIndex[1]+1)
            value = self.isPlayersPiece(board[nextPoint[0]-1][nextPoint[1]], player)
            type = self.quadsDict[quadIndex].changeSingleCell(nextPoint, value)
        if quadIndex[0] < spinIndex[0]:
            #upper quad change
            value = self.isPlayersPiece(board[spinIndex[0]+1][spinIndex[1]], player)
            self.quadsDict[quadIndex].changeSingleCell(spinIndex, value)
            nextPoint = (spinIndex[0], spinIndex[1]+1)
            value = self.isPlayersPiece(board[spinIndex[0]][spinIndex[1]], player)
            type = self.quadsDict[quadIndex].changeSingleCell(nextPoint, value)
        if quadIndex[1] < spinIndex[1]:
            #left quad change
            value = self.isPlayersPiece(board[spinIndex[0]+1][spinIndex[1]], player)
            self.quadsDict[quadIndex].changeSingleCell(spinIndex, value)
            nextPoint = (spinIndex[0]+1, spinIndex[1])
            value = self.isPlayersPiece(board[spinIndex[0]+1][spinIndex[1]+1], player)
            type = self.quadsDict[quadIndex].changeSingleCell(nextPoint, value)
        if quadIndex[1] > spinIndex[1]:
            #right quad change
            value = self.isPlayersPiece(board[spinIndex[0]][spinIndex[1]], player)
            self.quadsDict[quadIndex].changeSingleCell(quadIndex, value)
            nextPoint = (spinIndex[0]+1, spinIndex[1]+1)
            value = self.isPlayersPiece(board[spinIndex[0]][spinIndex[1]+1], player)
            type = self.quadsDict[quadIndex].changeSingleCell(nextPoint, value)
        return type
        
    def getOneChangeSpinIndexs(self, point):
        '''
        Get all quads that require only one change after a spin
        @param point: change quad index
        @return: list of quad indexs 
        '''
        change = [(point[0]-1, point[1]-1), (point[0]+1, point[1]-1),
             (point[0]+1, point[1]+1),(point[1]-1, point[1]+1)]
        return change
    
    def getTwoChangesSpinIndexs(self, point):
        '''
        Get all quads that require two changes after a spin
        @param point: change quad index
        @return: list of quad indexs 
        '''
        change = [(point[0]  , point[1]-1),(point[0]-1, point[1]),
            (point[0]+1, point[1]), (point[0]  , point[1]+1)]
        return change
    
    def getSpinChangedQuadsIndexs(self, point):
        '''
        Get all quad indexes that where effected by a spin at *point*
        @param point: the upper-left corner of the spin
        @return: list of points
        '''
        positions = [point]
        positions.extend(self.getOneChangeSpinIndexs(point))
        positions.extend(self.getTwoChangesSpinIndexs(point))
        return positions
    
    
#from loa_game import BLACK, EMPTY, WHITE
#size = 8
#board = (   (' ', 'W', 'W', 'W', ' ', 'W', 'W', ' '),
#            ('B', ' ', ' ', ' ', ' ', ' ', ' ', 'B'),
#            (' ', ' ', 'W', ' ', 'B', ' ', ' ', ' '),
#            (' ', 'B', 'B', ' ', ' ', 'B', ' ', ' '),
#            ('B', ' ', 'B', ' ', ' ', ' ', ' ', 'B'),
#            ('B', ' ', ' ', ' ', ' ', ' ', ' ', 'B'),
#            ('B', ' ', ' ', ' ', ' ', ' ', ' ', 'B'),
#            (' ', 'W', 'W', 'W', 'W', 'W', 'W', ' '))
#for i in xrange(0, 8):
#    print board[i]
#board = (   (' ', 'W', 'W', 'W', ' ', 'W', 'W', ' '),
#            ('B', 'B', ' ', ' ', ' ', ' ', ' ', ' '),
#            ('B', ' ', 'W', 'B', 'B', ' ', ' ', ' '),
#            (' ', 'B', 'B', ' ', ' ', 'B', ' ', ' '),
#            ('B', ' ', 'B', ' ', ' ', ' ', ' ', ' '),
#            ('B', 'B', ' ', ' ', ' ', ' ', ' ', ' '),
#            ('B', ' ', ' ', ' ', ' ', ' ', ' ', ' '),
#            (' ', 'W', 'W', 'W', 'W', 'W', 'W', ' '))
#for i in xrange(0, 8):
#    print board[i]
##qb = Quads(size, board, BLACK)
#qw = Quads(size, board, WHITE)
#print "WHITE: ", qw.quadTypesCounts
##print "BLACK: ", qb.quadTypesCounts
#qw.spin((1,1), board, WHITE)
#print "AFTER SPIN: ", qw.quadTypesCounts
##print "BLACK: ", qb.quadTypesCounts, "Euler: ", qb.eulerNumber()
#print qw.quadsDict[(0,1)].board